package com.lee.algorithm.recursion;

/***
 * @description: 纸牌获胜
 * 给定一个整型数组arr，代表不同的纸牌排成一条线
 * 玩家A和玩家B一次拿走一张纸牌，每个玩家每次只能拿走最左或最右的纸牌
 * 规定玩家A先拿，玩家B后拿，玩家A和玩家B都聪明绝顶
 * 请返回最后获胜的分数
 * @author : 青石路
 * @date: 2021/12/24 22:21
 */
public class CardsInLine {

    public static int winScore(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return Math.max(before(arr, 0, arr.length-1), after(arr, 0, arr.length-1));
    }

    /**
     * 先手拿
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int before(int[] arr, int left, int right) {
        if (left == right) {
            return arr[left];
        }
        return Math.max(arr[left] + after(arr, left+1, right), arr[right] + after(arr, left, right-1));
    }

    /**
     * 后手拿
     * @param arr
     * @param left
     * @param right
     * @return
     */
    public static int after(int[] arr, int left, int right) {
        if (left == right) {
            return 0;
        }
        return Math.min(before(arr, left+1, right), before(arr, left, right-1));
    }
}
